A conventional method of generating a check matrix for an LDPC code will be explained below. FIG. 13 illustrates an LDPC encoding/decoding system. Reference numeral 101 denotes an encoder, 102 denotes a modulator, 103 denotes a channel, 104 denotes a demodulator, and 105 denotes a decoder. Prior to explanation of a conventional method of generating check matrixes for LDPC codes, encoding and decoding using LDPC codes are explained first.
At the sending side, the encoder 101 generates a check matrix H using a certain method. Then, a generator matrix G is derived from the following condition.
G:k×n matrix (where k is information-length and n is code-word length)
GHT=0 (where T is transposition)
The encoder 101 then receives a message (m1 m2 . . . mk) of an information-length k, and generates a code-word C using the generator matrix G as follows:
                    C        =                              (                                          m                1                            ⁢                                                          ⁢                              m                2                            ⁢                                                          ⁢              …              ⁢                                                          ⁢                              m                k                                      )                    ⁢          G                                        =                              (                                          c                1                            ⁢                                                          ⁢                              c                2                            ⁢                                                          ⁢              …              ⁢                                                          ⁢                              c                n                                      )                    ⁢                                    (                                                where                  ⁢                                                                          ⁢                                                            H                      ⁡                                              (                                                                              c                            1                                                    ⁢                                                                                                          ⁢                                                      c                            2                                                    ⁢                                                                                                          ⁢                          …                          ⁢                                                                                                          ⁢                                                      c                            n                                                                          )                                                              T                                                  =                0                            )                        .                              
The modulator 102 subjects the generated code-word C to digital modulation such as BPSK, QPSK or multi-valued QAM and transmits the resultant modulated signal.
At the receiving side, the demodulator 104 receives the modulated signal via the channel 103, and subjects it to a digital demodulation such as BPSK, QPSK or multi-valued QAM. The decoder 105 then subjects the LDPC-coded, demodulated result to an iterative decoding by “Sum-Product Algorithm” and provides an estimated result (corresponding to the original m1 m2 . . . mk).
Conventionally, check matrixes for the LDPC codes are generated as explained below. As the check matrix the LDPC code, for example, following matrix is proposed by Gallager (see Non-patent Literature 1, FIG. 14).
This matrix is a binary matrix of “1” and “0”. Parts of “1” are hatched and parts of “0” are white. There are four “1”s in one row (hereinafter, “row weight”), and there are three “1”s in one column (hereinafter, “column weight”). All columns and rows have respective uniform weights. Thus, it is generally called “Regular-LDPC Code”. In the Gallager's codes, as shown in FIG. 14, the matrix is divided into three blocks, for example, and the second and third blocks are subjected to random permutation.
Because the random permutation has no certain rule, it is required to execute a time-consuming search by computer to find codes with a better characteristic.
Euclidean geometry codes are such LDPC codes that exhibit a relatively stable and nice characteristic and can definitely generate a matrix without the use of the computer search. Y. Kou et al. have proposed a method using such Euclidean geometry codes. This method explains “Regular-LDPC Codes” consisting of regular ensembles (see Non-patent Literature 2).
A method of generating a check matrix for LDPC codes is herein proposed using Euclidean geometry codes EG(2, 26) or a kind of finite geometric codes. This method achieves a characteristic that is located closely but 1.45 decibels away from the Shannon limit at an error rate of 10-4. FIG. 15 illustrates a configuration of Euclidean geometry codes EG(2, 22), which has a structure of “Regular-LDPC Codes” with row and column weights of 4, 4.
Euclidean geometry codes EG(m, 2s) have a characteristic defined as follows                Code length: n=22s−1        Redundant bit length: n−k=3s−1        Information length: k=22s−3s         Minimum distance: dmin=2s′+1        Density: r=2s′/(22s−1).        
As can be seen from FIG. 15, Euclidean geometry codes have a structure with a cyclically sifted location of “1” in each row from an adjacent row. This structure can characteristically configure codes easily and definitely.
The check matrix generating method by Y. Kou et al. further includes changing row and column weights based on the Euclidean geometry codes to extend rows and columns, if required. For example, when a column weight in EG(2, 22) is separated into halves, in the paper by Y. Kou et al., every other one of four weights located in one column is separated into two groups. FIG. 16 illustrates an exemplary regular separation of the column weight from 4 into 2.
On the other hand, Ludy et al. have reported that “Irregular-LDPC Codes” have a better characteristic than that of “Regular-LDPC Codes” (see Non-patent Literature 3). The “Irregular-LDPC Codes” represent such LDPC codes that have non-uniformity in either or both of row and column weights.
Richardson et al. have analyzed it theoretically (see Non-patent Literature 4) as well as Chung et al. (see Non-patent Literature 5).
In particular, Chung et al. analyze a “Sum-Product Algorithm” for LDPC codes, on the assumption that a log-likelihood-ratio (LLR) between an input and an output at an iterative decoder can be approximated in a Gaussian distribution, to derive a nice ensemble of row and column weights.
Non-patent Literature 1
R. G. Gallager, “Low-Density Parity-Check Codes”, Cambridge, MA: MIT Press, 1963.
Non-patent Literature 2
Y. Kou, S. Lin, and M. P. C. Fossorier, “Low Density Parity Check Codes Based on Finite Geometries: A Rediscovery,” ISIT 2000, pp. 200, Sorrento, Italy, Jun. 25 to 30, 2000.
Non-patent Literature 3
M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman, “Improved Low-Density Parity-Check Codes Using Irregular Graphs and Belief Propagation,” Proceedings of 1998 IEEE International Symposium on Information Theory, pp. 171, Cambridge, Mass., Aug. 16 to 21, 1998.
Non-patent Literature 4
T. J. Richardson and R. Urbanke, “The capacity of low-density parity-check codes under message-passing decoding,” IEEE Trans. Inform. Theory, vol. 47, No. 2, pp. 599 to 618, February 2001.
Non-patent Literature 5
S.-Y. Chung, T. J. Richardson, and R. Urbanke, “Analysis of Sum-Product Decoding of Low-Density Parity-Check Codes Using a Gaussian Approximation,” IEEE Trans. Inform. Theory, vol. 47, No. 2, pp. 657 to 670, February 2001:
In the conventional method of generating check matrixes for LDPC codes by Chung et al., however, the number of “1” points in a row (corresponding to a degree distribution of variable nodes later described) and the number of “1” points in a column (corresponding to a degree distribution of check nodes later described) are both employed. as variables to derive the degree distribution of variable nodes and the degree distribution of check nodes that can maximize the following equation (1) (rate: coding rate). In a word, a linear programming is employed to search an ensemble that minimizes a signal-to-noise ratio (SNR).
                    rate        =                  1          -                                                    ∫                0                1                            ⁢                              ρ                ⁡                                  (                  x                  )                                                                                    ∫                0                1                            ⁢                              λ                ⁡                                  (                  x                  )                                                                                        (        1        )            
Therefore, a problem arises because a check matrix derived from the maximum of the “rate” has a flux and unstable characteristic. In addition, the conventional method of generating check matrixes for LDPC codes iteratively executes the derivation of the degree distribution of variable nodes and the derivation of the degree distribution of check nodes over certain times. Therefore, a problem arises because it takes time to some extent for searching.
The present invention has been achieved in consideration of the above problems, and accordingly has an object to provide a method and an apparatus for generating a check matrix of a satisfactory performance for the an LDPC code capable of easily searching a definite and characteristic stabilized check matrix for the LDPC code corresponding to an optional ensemble.